package Offer;


import java.util.HashMap;
import java.util.Map;

/*重建 二叉树
*
* */
public class Offer07buildTree {
    Map<Integer,Integer> map=new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder){
        int n=inorder.length;
        for(int i=0;i<n;i++){
            map.put(inorder[i],i);
        }
        return myBuild(preorder,inorder,0,n-1,0,n-1);
    }

    private TreeNode myBuild(int[] preorder, int[] inorder, int pre_left, int pre_right, int ino_left, int ino_right) {
        //递归终止条件，左边界大于有边界
        if(pre_left>pre_right){
            return null;
        }
        int in_root=map.get(preorder[pre_left]);
        int subSize=in_root-pre_left;
        TreeNode root = new TreeNode(preorder[pre_left]);
        root.left=myBuild(preorder,inorder,pre_left+1,pre_right+subSize,ino_left,in_root-1);
        root.right=myBuild(preorder,inorder,pre_left+subSize+1,pre_right,in_root+1,ino_right);
        return root;
    }
}
